Masala #0558

Lochinbek so'ngi kunlarda Z-funksiya mavzusida ko'p bilimlarga ega bo'ldi. U bilib olgan narsalari quyidagilar edi.

1. $S$ satr deb $S_1S_2S_3....S_{|s|}$ ko'rinishdagi satrga aytiladi. Bu yerda $S_i$  bu $S$ satrning elementlari $|S|$ esa $S$ satrning uzunligi.
2. $S[i..j] (1 ≤ i ≤ j ≤ |S|)$ qism satr deb $S_iS_{i + 1}...S_j$ ko'rinishdagi satrga aytiladi.
3. $S$ satrning $L (1 ≤ L ≤ |S|)$  uzunlikdagi prefiksi deb $S[1..L]$ satrga aytiladi.
4. $S$ satrning $L (1 ≤ L ≤ |S|)$  uzunlikdagi suffiksi deb $S[|S|-L+1..|S|]$ satrga aytiladi.

Sizning vazifangiz $S$ satrda ham prefiks, ham suffiks bo'la oladigan qism satrlar nechtaligini qaniqlash.

Bitta qatorda kichik lotin harflaridan tashkil topgan $S_1S_2...S_{|s|} (1 ≤ |S| ≤ 10^5)$ satr.

Birinchi qatorda $K$ soni. $K$-ham prefiks ham suffiks bo'la oladigan satrlar soni.
Keyingi $K$ ta qatorda esa $L_i C_i$ sonlari. $Li$ ham prefiks ham suffiks bo'luvchi satr uzunligi $C_i$ esa shu prefiks(suffiks) $S$ satrda jami necha marotaba qism satr bo'lib kelganligi. $L_i C_i$ juftliklari $L_i$ o'sish tartibiga ko'ra chiqarilsin.